package tree.easy;

import tree.TreeNode;

/**
 * 110. 平衡二叉树
 */
public class isBalanced {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(3, new TreeNode(1), new TreeNode(6)), new TreeNode(8, new TreeNode(7), new TreeNode(9)));
        System.out.println(new isBalanced().isBalanced(root));
        System.out.println(new isBalanced().height(root));
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 计算每个节点子树的最大深度并比较
        if (Math.abs(height(root.left) - height(root.right)) >= 1) {
            return false;
        }
        return  isBalanced(root.left) && isBalanced(root.right);
    }

    /**
     * 计算节点最大深度
     * @param node
     * @return
     */
    public int height(TreeNode node) {
        if (node ==  null) {
            return 0;
        }
        return Math.max(height(node.left) + 1, height(node.right) + 1);
    }
}
